CopyOnWriteArrayList 详解

发表于 | | 阅读次数

CopyOnWriteArrayList 详解

介绍 CopyOnWriteArrayList 之前，先看一下 ArrayList 的使用:

1
2
3
4
5
6
7
8
9
10
11
public static void main(String... args) {
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    for (String s:list){
        if ("3".equals(s)){
            list.remove(s);
        }
    }
}

执行上面的代码后 jvm 会抛出 ConcurrentModificationException 的异常:

Exception in thread “main” java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at com.example.lib.MyClass.main(MyClass.java:13)

根据报错的堆栈信息可知，异常是在 ArrayList 内部类 Itr 的 checkForComodification 方法抛出的。

反编译 java 代码后，字节码代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String... args) {
    List<String> list = new ArrayList();// 9
    list.add("1");// 10
    list.add("2");// 11
    list.add("3");// 12
    Iterator var2 = list.iterator();// 13
    while(var2.hasNext()) {
        String s = (String)var2.next();
        if ("3".equals(s)) {// 14
            list.remove(s);// 15
        }
    }
}// 18

由字节码可知，foreach 语法糖实际上是利用了迭代器来完成遍历。

先调用 iterator 方法得到迭代器对象

1
2
3
public Iterator<E> iterator() {
    return new Itr();
}

该方法返回的是 ArrayList 的内部类 Itr 对象。Itr 类代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    Itr() {}
    public boolean hasNext() {
        return cursor != size;
    }
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

next() 方法会先调用 checkForComodification 方法判断 modCount 与 expectedModCount 是否相等，如果不等的话就抛出异常。

对于 expectedModCount ，当创建 Itr 对象的时候会默认赋值为 modCount。当新增或者删除元素的时候会执行 modCount++ ，所以ArrayList 遍历的时候是不允许新增或者删除元素的，那就无法支持多线程的读写操作了。

java 的并发包 java.util.concurrent 里提供的 CopyOnWriteArrayList 是线程安全的，支持多线程并发读写操作。下面以 JDK1.8 源码分析一下实现原理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}
1
2
3
4
5
6
7
8
9
public E get(int index) {
    return get(getArray(), index);
}
private E get(Object[] a, int index) {
        return (E) a[index];
}
final Object[] getArray() {
        return array;
}

由源码可知，CopyOnWriteArrayList 在新增或者删除元素，先获取可重入锁 ReentrantLock，拷贝原来的数组，在新的数组上面新增或者删除元素。CopyOnWriteArrayList 在读取元素的时候，直接在老数组上读取。CopyOnWriteArrayList 的读写操作是在不同的数组上面操作的，保证了多线程操作的安全性。